SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

The `!multidimensional assignment problem`! (MAP) is a fundamental `F33f`_`[combinatorial optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Combinatorial_optimization]`_`f problem which was introduced by William Pierskalla.`:cite-ref-pier68-1-0[`F5bf`_`[1`#cite-note-pier68-1]`_`f] This problem can be seen as a generalization of the linear `F33f`_`[assignment problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Assignment_problem]`_`f.`:cite-ref-pasi21-2-0[`F5bf`_`[2`#cite-note-pasi21-2]`_`f] In words, the problem can be described as follows:

An instance of the problem has a number of `*agents`* (i.e., `*cardinality`* parameter) and a number of `*job characteristics`* (i.e., `*dimensionality`* parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some `*cost`*. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the `*total cost`* of assigning the agents so that the assignment of agents to each job characteristic is an `F33f`_`[injective function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Injective_function]`_`f, or `F33f`_`[one-to-one function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=One-to-one_function]`_`f from agents to a given job characteristic.

Alternatively, describing the problem using graph theory:

The multidimensional assignment problem consists of finding, in a `F33f`_`[weighted`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Weighted_graph]`_`f `F33f`_`[multipartite graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multipartite_graph]`_`f, a `F33f`_`[matching`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Matching_(graph_theory)]`_`f of a given size, in which the sum of weights of the edges is minimum.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f]

>>Contents

• `F0af`_`[Formal definition`#formal-definition]`_`f

• `F0af`_`[Problem parameters`#problem-parameters]`_`f

• `F0af`_`[Size of cost array`#size-of-cost-array]`_`f

• `F0af`_`[Number of feasible solutions`#number-of-feasible-solutions]`_`f

• `F0af`_`[Computational complexity`#computational-complexity]`_`f

• `F0af`_`[Applications`#applications]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Formal definition

Various formulations of this problem can be found in the literature. Using cost-functions, the `! D {\\displaystyle D} –dimensional assignment problem`! (or `! D {\\displaystyle D} –MAP`!) can be stated as follows:

Given D {\\displaystyle D} sets, A {\\displaystyle A} and J 1 , … … J D − − 1 {\\displaystyle J_{1},\\ldots J_{D-1}} , of equal size, together with a cost `F33f`_`[array`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Array]`_`f or multidimensional `F33f`_`[weight function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Weight_function]`_`f C {\\displaystyle C} : A × × J 1 × × … … × × J D − − 1 → → R + {\\displaystyle A\\times J_{1}\\times \\ldots \\times J_{D-1}\\rightarrow \\mathbb {R} _{+}} , find D − − 1 {\\displaystyle D-1} `F33f`_`[permutations`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Permutation]`_`f π π d {\\displaystyle \\pi _{d}} : `*A`* → J d {\\displaystyle J_{d}} such that the total `F33f`_`[cost function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Loss_function]`_`f: ∑ ∑ a ∈ ∈ A C ( a , π π 1 ( a ) , … … , π π D − − 1 ( a ) ) {\\displaystyle \\sum _{a\\in A}C(a,\\pi _{1}(a),\\ldots ,\\pi _{D-1}(a))}

is minimized.`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]

>>>Problem parameters

The multidimensional assignment problem (MAP) has two key parameters that determine `*the size of a problem instance`*:

1. The `!`F33f`_`[dimensionality`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimension]`_`f parameter`! D {\\displaystyle D}

2. The `!`F33f`_`[cardinality`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cardinality]`_`f parameter`! N = | A | {\\displaystyle N=|A|} , where | A | {\\displaystyle |A|} denotes the number of elements in A {\\displaystyle A} .

>>>Size of cost array

Any problem instance of the MAP with parameters D , N {\\displaystyle D,N} has its specific `!cost array`! C {\\displaystyle C} , which consists of N D {\\displaystyle N^{D}} instance-specific costs/weights parameters C ( a , a 1 , … … , a D − − 1 ) {\\displaystyle C(a,a_{1},\\ldots ,a_{D-1})} . N D {\\displaystyle N^{D}} is the `*size`* of cost array.

>>>Number of feasible solutions

The `F33f`_`[feasible region or solution space`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feasible_region]`_`f of the MAP is very large. The number K {\\displaystyle K} of feasible solutions (the size of the MAP instance) depends on the MAP parameters D , N {\\displaystyle D,N} . Specifically, K = ( N ! ) D − − 1 {\\displaystyle K=(N!)^{D-1}} .`:cite-ref-pasi21-2-1[`F5bf`_`[2`#cite-note-pasi21-2]`_`f]

>>Computational complexity

The problem is generally `F33f`_`[NP-hard`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-hard]`_`f. In other words, there is no known `F33f`_`[algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algorithm]`_`f for solving this problem in polynomial time, and so a long computational time may be needed for solving problem instances of even moderate size (based on dimensionality and cardinality parameters).`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]

>>Applications

The problem found application in many domains:

• `F33f`_`[Scheduling (production processes)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Scheduling_(production_processes)]`_`f`:cite-ref-pier68-1-1[`F5bf`_`[1`#cite-note-pier68-1]`_`f]

• `F33f`_`[Multi-sensor data fusion`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_fusion]`_`f`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f]

• `F33f`_`[Record linkage or multipartite entity resolution`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Record_linkage]`_`f`:cite-ref-pasi21-2-2[`F5bf`_`[2`#cite-note-pasi21-2]`_`f]

• `F33f`_`[Elementary particle physics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Particle_physics]`_`f`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f]

• `F33f`_`[Fall detection in elderly with small wearable devices`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Medical_alarm]`_`f`:cite-ref-8[`F5bf`_`[8`#cite-note-8]`_`f]

>>References

`:cite-note-pier68-1`!1.`! `F0af`_`[↑`#cite-ref-pier68-1-0]`_`f `:citerefpierskalla1968`aPierskalla, William P. (1968). "Letter to the Editor—The Multidimensional Assignment Problem". `*Operations Research`*. `!16`! (2). INFORMS: 422–431. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1287/opre.16.2.422.

`:cite-note-pasi21-2`!2.`! `F0af`_`[↑`#cite-ref-pasi21-2-0]`_`f `:citerefkammerdinersemenovpasiliao2021`aKammerdiner, Alla; Semenov, Alexander; Pasiliao, Eduardo (2021). "Multidimensional Assignment Problem for multipartite entity resolution". `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:2112.03346 [cs.DM].

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citerefnatudatenagi2020`aNatu, Shardul; Date, Ketan; Nagi, Rakesh (2020). "GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs". `*Parallel Computing`*. `!97`!: 102666. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.parco.2020.102666. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0167-8191. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 221667518.

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `:citerefkarapetyangutin2011`aKarapetyan, Daniel; Gutin, Gregory (2011-06-01). "Local search heuristics for the multidimensional assignment problem" (PDF). `*Journal of Heuristics`*. `!17`! (3): 201–249. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s10732-010-9133-3. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1572-9397. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 3446729.

`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f `:citerefnguyenle-thipham-dinh2012`aNguyen, Duc Manh; Le Thi, Hoai An; Pham Dinh, Tao (2012-10-12). "Solving the Multidimensional Assignment Problem by a Cross-Entropy method". `*Journal of Combinatorial Optimization`*. `!27`! (4): 808–823. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s10878-012-9554-z. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1382-6905. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 254658376.

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f `:citerefpoore1994`aPoore, Aubrey B. (1994). "Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking". `*Computational Optimization and Applications`*. `!3`! (1): 27–57. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/BF01299390. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 33848795.

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f `:citerefpusztaszerirensingliebling1996`aPusztaszeri, Jean-François; Rensing, Paul E.; Liebling, Thomas M. (1996). "Tracking elementary particles near their primary vertex: a combinatorial approach". `*Journal of Global Optimization`*. `!9`! (1): 41–64. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/BF00121750. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 2002168.

`:cite-note-8`!8.`! `F0af`_`[↑`#cite-ref-8]`_`f `:citerefkammerdinerguererro2019`aKammerdiner, Alla R.; Guererro, Andre N. (2019). "Data-driven combinatorial optimization for sensor-based assessment of near falls". `*Annals of Operations Research`*. `!276`! (1–2): 137–153. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s10479-017-2585-1. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0254-5330. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 254223885.

`c`F0af`_`[↑ Back to top`#top]`_`f`a